//lc23合并k个链表
//所有链表都按升序排列，将所有链表按升序合并成一个新链表
/*
要合并k个链表，可以先合并两个链表，合成的新链表再依次合并其他链表
或者采用分治法，每两两链表合并，得到的新链表组再进行两两合并。。。
*/
#include <vector>
using std::vector;
class ListNode
{
public:
    int val;
    ListNode* next;
    ListNode(): val(0),next(nullptr) {}
    ListNode(int x) :val(x),next(nullptr){}
    ListNode(int x,ListNode* next):val(x),next(next){}
};

//首先看如何将两个链表进行合并
ListNode* mergeTwoLists(ListNode* list1,ListNode* list2)
{
    if((!list1)||(!list2))  return list1? list1:list2;
    ListNode* result=new ListNode();
    ListNode* cur=result;
    while(list1&&list2) //当两个链表都有结点时，进行合并
    {
        if(list1->val >= list2->val)
        {
            cur->next=list2;    //将list1结点直接连接到result链表中，不需要重新开一个链表
            list2=list2->next;
        }
        else
        {
            cur->next=list1;
            list1=list1->next;
        }
        cur=cur->next;   
    }
    //最后只剩一个链表有结点
    cur->next=list1? list1:list2;
    return result->next;
}

//第一种合并方法：
ListNode* mergeKLists(vector<ListNode*>& lists)
{
    ListNode* ans=nullptr;
    for(int i=0;i<lists.size();i++)
        ans=mergeTwoLists(ans,lists[i]);
    return ans;

}


//递归，分治法
ListNode* merge(vector<ListNode*>& lists,int left,int right)
{
    if(left==right) return lists[left];
    if(left>right)  return nullptr;
    int mid=(left+right)/2;
    return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right));

}

ListNode* mergeKLists_2(vector<ListNode*>& lists)
{
    return merge(lists,0,lists.size()-1);
}

